home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / GRAPHICS / SPRCOL.ZIP / SPRCOL.TXT
Encoding:
Text File  |  1996-04-26  |  4.4 KB  |  175 lines
  1.  
  2.         A Pixel-Precision Method For Detecting Sprite Collision
  3.  
  4.                                 v 1.0
  5.  
  6.                            by Mark Mackey
  7.  
  8.  
  9. ---
  10.  
  11. Introduction
  12.  
  13. ----
  14.  
  15.  
  16. A common query on the USENET newsgroup rec.games.programmer over the 
  17.  
  18. years has been how to do fast pixel-precision collision detection. A 
  19.  
  20. number of people have presented some excellent algorithms for extending 
  21.  
  22. and speeding up bounding-box collision detection between large numbers of 
  23.  
  24. objects (for instance, dividing the play area into subfields and sorting 
  25.  
  26. the sprites into these subfields, thus greatly reducing the number of 
  27.  
  28. sprite-sprite collisions that have to be checked in the first place). 
  29.  
  30.  
  31. However, there have been little information available on how to detect 
  32.  
  33. collisions efficiently at the pixel level. I thus present here some code 
  34.  
  35. from my game XQuest (blatant plug) which checks for collisions at the 
  36.  
  37. pixel level. The routine assumes that the bounding boxes for the two 
  38.  
  39. sprites overlap, and hence should be relatively easy to add to an 
  40.  
  41. existing bounding-box collision detection routine. This code is fast, 
  42.  
  43. relatively efficient in terms of space (requiring 4 bytes per row of each 
  44.  
  45. sprite), and even works! The one limitation is that sprites are assumed 
  46.  
  47. to be 32 pixels or less in width. For larger sprites, you could either 
  48.  
  49. treat them as 2 or more 32-pixel wide objects, or with a bit of creative 
  50.  
  51. thought this routine could be rewritten to allow for 64-pixel wide 
  52.  
  53. objects on the 386 (left as an exercise for the reader :). 
  54.  
  55.  
  56. The code in the enclosed file COLLIDE.PAS is organised as a Turbo Pascal 
  57.  
  58. unit, but all of the essential code is in assembly language and could be 
  59.  
  60. easily ported to work under C or in a pure asm program. If any of the 
  61.  
  62. Pascalisations confuse you just let me know and I'll explain :). Also, if 
  63.  
  64. you need a version of this code to work on a 286 then let me know and 
  65.  
  66. I'll send it to you (but be warned: it's not nearly as nice :).
  67.  
  68.  
  69. ---
  70.  
  71. The Algorithm 
  72.  
  73. ---
  74.  
  75.  
  76. The first step is to create a 'transparency' mask for each sprite. The 
  77.  
  78. mask consists of a dword for each row of the sprite, with each bit being 
  79.  
  80. a 0 if the corresponding pixel is 'empty', and a 1 otherwise. For 
  81.  
  82. example, if a row of your sprite looked like (colour indexes, 0 being 
  83.  
  84. transparent) 
  85.  
  86.  
  87. 0  0  0  1  23  42  0  1  56  0  0  0  0  0 
  88.  
  89.  
  90. the the corresponging mask bytes would be 
  91.  
  92.  
  93. 00011101 10000000 00000000 00000000 =  1D 80 00 00 
  94.  
  95.  
  96. The MakeMask procedure given will produce such a mask from a sprite 
  97.  
  98. supplied in the XLib linear bitmap format (with pixels of colour zero 
  99.  
  100. being transparent), and is easily adaptable to your own sprite format. 
  101.  
  102.  
  103. OK, now the hard part. We have found in our general-purpose bounding-box 
  104.  
  105. collision detection routine that two sprites' bounding boxes have 
  106.  
  107. collided (ie their masks overlap). 
  108.  
  109.  
  110. Let the leftmost sprite have (x1,y1) as the coords of its top left 
  111.  
  112. corner, and the rightmost one (x2,y2). Take the mask entry for row 
  113.  
  114. |y2-y1| of the topmost sprite and shift it left by the difference in the 
  115.  
  116. x-coordinates (x2-x1). AND this value with the 1st mask entry of the 
  117.  
  118. lower sprite. If the result is non-zero then a collision occurred on this 
  119.  
  120. row. If not, then shift row |y2-y1+1| and compare it to row 2 of the 
  121.  
  122. lower sprite, and so on, until you reach the bottom of one of the 
  123.  
  124. sprites. If no collision has been detected by this time, then the sprites 
  125.  
  126. didn't collide. Simple, eh? 
  127.  
  128.  
  129. This routine is quite fast, requiring only a MOV, a SHL and an AND for
  130.  
  131. each row checked, and only checking those rows that overlap.
  132.  
  133.  
  134. ---
  135.  
  136. The Legal Bit
  137.  
  138. ---
  139.  
  140.  
  141. This software is (C) Copyright 1995 Mark Mackey. Permission is given to 
  142.  
  143. distribute this code freely, or to distribute modified forms of this 
  144.  
  145. software provided that the author is acknowledged and this copyright 
  146.  
  147. notice retained. Permission is also given to utilise this code in 
  148.  
  149. original or modified form in any software provided that the author is 
  150.  
  151. acknowledged. 
  152.  
  153.  
  154. I can be contacted by
  155.  
  156.  
  157. Email: mdm1004@cus.cam.ac.uk 
  158.  
  159. WWW: http://www.ch.cam.ac.uk/MMRG/mdm.html
  160.  
  161. Snail: c/o Trinity Hall,
  162.  
  163.            Cambridge CB2 1TJ
  164.  
  165.            UK
  166.  
  167.  
  168. These addresses will be in use until at least October 1996. Please let me 
  169.  
  170. know if you found this code helpful/useful/rubbish/whatever or if you 
  171.  
  172. improve it :) 
  173.  
  174.  
  175.